/*
                           Compression File
	This Program is designed to Compress the input file given by the user
and create the Compressed file with specified name or with same name having 
extensiom as ".cmp".	
*/
//============================================================================
//Block of Header Files Used In Program
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<fcntl.h>
#include<time.h>
#include<sys/stat.h>
//============================================================================
//Data Structures Used In Program

//This Structure is Used To Manipulate Header of Compression
struct header
{
  char ch;
  int cnt;
  unsigned long  code;
  unsigned int depth;
  unsigned int tot_node;
  struct header * next;
};
//This Structure is Used To Manipulate List of Characters of Input File
struct list
{
  char ch;
  int  cnt;
  char st;
  int  isparent;
  int  code;
  int  depth;
  struct list *prev;
  struct list *next;
  struct list *lchild;
  struct list *rchild;
};
//=============================================================================
//Global Declaration of Variables And Prototypes of Functions used
struct header *head_header=NULL;
static unsigned int ENO=4294967168;
void code_tree(struct list *,int,int);
int compress(char[],char[]);
//=============================================================================
//This function is Used for converting the Exceding Number 
//i.e. Number which is greater then 127
unsigned long excedify(no)
unsigned long no;	
{
	int rem;
	if(no>ENO)
	{
		rem=no-ENO;
		no=128+rem;
	}
	if(no==ENO)
		no=128;
  return(no);
}
//=============================================================================
//This function checks that given file name is of directory or ordinay file
int DirectoryOrFile(filename,arg)
char* filename;
int arg;
{
	struct stat statbuf;
	int fd;
	stat(filename,&statbuf);
	if(arg==1)
	   if(statbuf.st_mode & S_IFDIR)
   	   {
		printf("\nGiven File '%s' is a directory\n",filename);
		printf("This utility can't compress the directory\n");
		exit(0);
 	   }
		   
	if(arg==4)
	   if(statbuf.st_mode & S_IFDIR)
   	   {
		printf("\nDestination File '%s' is a directory\n",filename);
		printf("This utility can't compress file in directory\n");
		 exit(0);
 	   }
	return 0;
}
//============================================================================
//This Function is Used To find Ratio of Files
int ratio(fnmR,fnmW)
char fnmR[15];
char fnmW[15];
{
	struct stat statbuf;
	long orgfilesize;
	int fileratio;
	//Status of original file
	stat(fnmR,&statbuf);
	printf("\nStatus of file ''%s''",fnmR);
	printf("\nSize of file in bytes %ld",statbuf.st_size);
	printf("\nLast file accessed time and date %s",ctime(&statbuf.st_ctime));
	orgfilesize=statbuf.st_size;
	//Status of compressed file
	stat(fnmW,&statbuf);
	printf("\nStatus of compressed file ''%s''",fnmR);
	printf("\nSize of file in bytes %ld",statbuf.st_size);
	printf("\nLast file accessed time and date %s",ctime(&statbuf.st_ctime));
	fileratio=(statbuf.st_size*100)/orgfilesize;
	printf("\nCompression ratio is %d%\n",fileratio);
			
}
//============================================================================= 
//This Function is used for Creation of List of Characters of Input File
int make_list(head,ch)
struct list **head;
char *ch;
{
    struct list *temp=*head,*temp1;
    while(temp!=NULL)
    {
     if(temp->ch==*ch)
     {
       temp->cnt++;
       return 0;
      }
     else
      temp=temp->next;
    }
    temp=*head;
    if(temp==NULL)
    {
      temp=(struct list *)malloc(sizeof(struct list));
      temp->ch=*ch;
      temp->cnt=1;
      temp->st='n';
      temp->isparent=0;
      temp->code=0;
      temp->depth=0;
      temp->prev=NULL;
      temp->next=NULL;
      temp->lchild=NULL;
      temp->rchild=NULL;
      *head=temp;
    }
    else
    {
      while(temp->next!=NULL)
       temp=temp->next;
      temp1=(struct list *)malloc(sizeof(struct list));
      temp1->ch=*ch;
      temp1->cnt=1;
      temp1->st='n';
      temp1->isparent=0;
      temp1->code=0;
      temp1->depth=0;
      temp1->prev=temp;
      temp1->next=NULL;
      temp1->lchild=NULL;
      temp1->rchild=NULL;
      temp->next=temp1;
    }
    return 0;
}
//=============================================================================
//This function is Used for Finding the Two Nodes having Minimum Frequencies      From List of Characters
int find_min(head,min1,min2)
struct list **head;
struct list **min1;
struct list **min2;
{
   struct list *temp;

   while((*min1)->st=='s')
     (*min1)=(*min1)->next;
   while((*min2)->st=='s')
     (*min2)=(*min2)->next;
   if((*min1)==(*min2))
   {
      if((*min1)->next==NULL)
       return 1;
      else
       do
       {
	(*min2)=(*min2)->next;
       }while((*min2)->st!='n'&&(*min2)->next!=NULL);

   }
   if((*min1)->cnt>(*min2)->cnt)
    {
     temp=(*min1);
     (*min1)=(*min2);
     (*min2)=temp;
    }

   temp=*head;
   while(temp!=NULL)
   {
     if(temp->st=='n')
     {
      if(temp->cnt <= (*min1)->cnt&&temp->ch!=(*min1)->ch)
      {
	 if(temp!=(*min2))
	 {
	  (*min2)=(*min1);
	  (*min1)=temp;
	 }
	  temp=temp->next;
	  continue;
      }
      if(temp->cnt <= (*min2)->cnt&&temp->ch!=(*min2)->ch)
      {
	 if(temp!=(*min1))
	  (*min2)=temp;
      }
     }
      temp=temp->next;
   }
   (*min1)->st='s';
   (*min1)->isparent=1;
   (*min2)->st='s';
   (*min2)->isparent=1;
   if((*min1)==(*min2))
     return 1;
   return 0;
}
//=============================================================================
//This Function is Used for Creation of Header of Compression
void create_header(head,node)
struct header **head;
struct list *node;
{
    struct header *temp=*head,*temp1;
    if(temp==NULL)
    {
     temp=(struct header *)malloc(sizeof(struct header));
     temp->ch=node->ch;
     temp->code=node->code;
     temp->depth=node->depth;
     temp->cnt=node->cnt;
     temp->tot_node=1;
     temp->next=NULL;
     *head=temp;
    }
    else
    {
     while(temp->next!=NULL)
	temp=temp->next;
     temp1=(struct header *)malloc(sizeof(struct header));
     temp1->ch=node->ch;
     temp1->code=node->code;
     temp1->depth=node->depth;
     temp1->cnt=node->cnt;
     temp1->tot_node=0;
     temp1->next=NULL;
     temp->next=temp1;
     (*head)->tot_node++;
    }
}
//=============================================================================
//This Function is Used To Code the Huffman's Tree
void code_tree(struct list *root,int codesofar,int depth)
{

  if(root->lchild==NULL&&root->rchild==NULL)
  {
	  root->code=codesofar;
	  root->depth=depth;
	  depth=0;
	  create_header(&head_header,root);
  }
  else
  {
     code_tree(root->lchild,(codesofar*2),depth+1);
     code_tree(root->rchild,((codesofar*2)+1),depth+1);
  }
}
//==============================================================================
//This Function is used for Creation of Huffman's Tree
void create_tree(head,min1,min2)
struct list **head;
struct list **min1;
struct list **min2;
{
   struct list *temp=*head,*temp1;
   while(temp->next!=NULL)
    temp=temp->next;
   temp1=(struct list *)malloc(sizeof(struct list));
   temp1->cnt=((*min1)->cnt + (*min2)->cnt);
   temp1->st='n';
   temp1->lchild=(*min1);
   temp1->rchild=(*min2);
   temp1->isparent=0;
   temp1->code=0;
   temp1->depth=0;
   temp1->next=NULL;
   temp->next=temp1;
}
//=============================================================================
//This Function is Used for Freeing the List of Characters
void free_list(head)
struct list **head;
{
   struct list *temp=*head;
   while(temp->next!=NULL)
    temp=temp->next;
   while(temp->prev!=NULL)
   {
     temp=temp->prev;
     free(temp->next);
   }
   free(*head);
}
//=============================================================================
//This Function is for compression of Input file
int compress(fnmR,fnmW)
char fnmR[15];
char fnmW[15];
{
  //Variable Block : Variables used in programes 
 //============================================================================
  int fpR,fpW,code,len,bit,rembit,i,size_cnt,cnt;
  unsigned int temp_code,temp_node,tempcodespace;
  unsigned long file_size=0,temp_file_size=0,codespace,mask=0,tempmask;
  char *ch,*char_write,*t,ext[3],ch_wrt[2],uch,lch;
  struct list *head_list=NULL,*min1,*min2,*temp;
  struct header *temph;
  //End of Variable Block
 //============================================================================ 
  ch=(char *)malloc(1);
  if((fpR=open(fnmR,O_RDONLY))==-1)
  {
    printf(" \n %s File not found",fnmR);
    exit(0);
  }
  //===========================================================================
  //Start To Read Input File
  else
  {
  //===========================================================================
  //Read Input File Character by Character And Create List of character
   while((read(fpR,ch,1))!=0)
   {
       make_list(&head_list,ch);
       file_size=file_size+1;
   }
  //End of Read File and Create List
  //===========================================================================
  //Find Min Two Node from list and Create Tree For Huffman & Create Codes
   temp=head_list;
   while(temp!=NULL)
   {
    min1=head_list;
    min2=head_list->next;
    if(find_min(&head_list,&min1,&min2)==1)
    {
     //Create Codes Here
     code_tree(min1,0,0);
     break;
    }
    //Creat Tree For Huffman Here
    create_tree(&head_list,&min1,&min2);
    temp=temp->next;
   }
  //End of Find Min Two Node from list and Create & Code Huffman Tree
  //============================================================================
 } 
 //End of Reading Input File 
//==============================================================================
 fcloseall();
 //end of creation of header
//=============================================================================
//Again Open Input File to Read 
 if((fpR=open(fnmR,O_RDONLY))==-1)
 {
    printf("\n %s File not found",fnmR);
    fcloseall();
    exit(0);
 }
 else
 {
//=============================================================================
//Fetch Input File Extension
   t=strstr(fnmR,".");
   if(t==NULL)
   {
	  strcpy(ext,"svv");
          ext[3]='\0';
   }
   else
   {
    i=0;
    t++;
    while(i<3)
    {
      ext[i++]=*t;
      t++;
    }
   ext[i]='\0';
   }
//End of Create New File Name And Fetch Input File Extension
//============================================================================
//Create New File  
   if((fpW=open(fnmW,O_WRONLY|O_CREAT|O_TRUNC,S_IWRITE|S_IREAD))==-1)
   {
    printf("\n %s File Already Exist OR Enable to create new file",fnmW);
    fcloseall();
    exit(0);
   }
   else
   {
     //Code to Write Header TotalNode To New File as 1 & 2 byte
     char_write=(char *)malloc(1);
     temp_node=head_header->tot_node;
     temp_node=temp_node>>8; 
     *char_write=(char)temp_node;
     if((write(fpW,char_write,1))!=1)
     {
       printf("\nFile writing error");
       fcloseall();
       exit(0);
     }
     temp_node=head_header->tot_node;
     temp_node=temp_node<<8;
     temp_node=temp_node>>8;
     *char_write=(char)temp_node;
     if((write(fpW,char_write,1))!=1)
     {
       printf("\nFile writing error");
       fcloseall();
       exit(0);
     }
  //End of Write Header TotalNode To New File 
//==============================================================================//Code To Write InputFile Extension as 3 & 4 & 5 byte To New File
  free(char_write);
  char_write=(char *)malloc(3);
  char_write=ext;
  strcpy(char_write,ext);
  if((write(fpW,char_write,3))!=3)
      {
       printf("\nFile writing error");
       fcloseall();
       exit(0);
      }
 //End of Write InputFile Extension To New File
//=============================================================================
//Code To Write InputFile size to New File as 6-10 bytes
  char_write=(char *)malloc(1);
  temp_file_size=file_size>>24;
  temp_file_size=temp_file_size<<8;
  temp_file_size=temp_file_size>>8;
  *char_write=(char)temp_file_size;
  if((write(fpW,char_write,1))!=1)
  {
    printf("\nFile writing error");
    fcloseall();
    exit(0);
  }
  char_write=(char *)malloc(1);
  temp_file_size=file_size>>16;
  temp_file_size=temp_file_size<<8;
  temp_file_size=temp_file_size>>8;
  *char_write=(char)temp_file_size;
  if((write(fpW,char_write,1))!=1)
  {
   printf("\nFile writing error");
   fcloseall();
   exit(0);
  }
  char_write=(char *)malloc(1);
  temp_file_size=file_size>>8;
  temp_file_size=temp_file_size<<8;
  temp_file_size=temp_file_size>>8;
  *char_write=(char)temp_file_size;
  if((write(fpW,char_write,1))!=1)
  {
    printf("\nFile writing error");
    fcloseall();
    exit(0);
  }
  char_write=(char *)malloc(1);
  temp_file_size=file_size;
  temp_file_size=temp_file_size<<8;
  temp_file_size=temp_file_size>>8;
  *char_write=(char)temp_file_size;
  if((write(fpW,char_write,1))!=1)
  {
   printf("\nFile writing error");
   fcloseall();
   exit(0);
  }
  //End of Write InputFile size to New File
 //=======================================================================      
 //Code To Calculate Header Size and Write To New File
  temph=head_header;
  codespace=0;
  tempcodespace=0;
  while (temph!=NULL)
  {
    if((temph->depth%8)>0)
      tempcodespace=(temph->depth/8)+2+1;
    else
      tempcodespace=(temph->depth/8)+2;
    codespace=codespace+tempcodespace;
    temph=temph->next;
   }
   tempcodespace=0;
   char_write=(char *)malloc(1);
   tempcodespace=codespace>>24;
   tempcodespace=tempcodespace<<8;
   tempcodespace=tempcodespace>>8;
   *char_write=(char)tempcodespace;
   if((write(fpW,char_write,1))!=1)
   {
     printf("\nFile writing error");
     fcloseall();
     exit(0);
   }
   tempcodespace=0;
   char_write=(char *)malloc(1);
   tempcodespace=codespace>>16;
   tempcodespace=tempcodespace<<8;
   tempcodespace=tempcodespace>>8;
   *char_write=(char)tempcodespace;
   if((write(fpW,char_write,1))!=1)
   {
     printf("\nFile writing error");
     fcloseall();
     exit(0);
   }
   tempcodespace=0;
   char_write=(char *)malloc(1);
   tempcodespace=codespace>>8;
   tempcodespace=tempcodespace<<8;
   tempcodespace=tempcodespace>>8;
   *char_write=(char)tempcodespace;
   if((write(fpW,char_write,1))!=1)
   {
     printf("\nFile writing error");
     fcloseall();
     exit(0);
    }
    tempcodespace=0;
    char_write=(char *)malloc(1);
    tempcodespace=codespace;
    tempcodespace=tempcodespace<<8;
    tempcodespace=tempcodespace>>8;
    *char_write=(char)tempcodespace;
    if((write(fpW,char_write,1))!=1)
    {
      printf("\nFile writing error");
      fcloseall();
      exit(0);
     }
  //End of Write Header Size to New File
//=============================================================================
  //Code to Write Header To New File as Char Depth Code
     temph=head_header;
     while(temph!=NULL)
     {
	free(char_write);
	char_write=(char *)malloc(1);
	//char_write=NULL;
	*char_write=(char)temph->ch;
	if((write(fpW,char_write,1))!=1)
	{
	  printf("\nFile writing error");
	  fcloseall();
	  exit(0);
	}
	free(char_write);
	char_write=(char *)malloc(1);
	//char_write=NULL;
	*char_write=(char)temph->depth;
	if((write(fpW,char_write,1))!=1)
	{
	  printf("\nFile writing error");
	  fcloseall();
	  exit(0);
	}
  //Break up Code into Parts if Depth > 8 and Write Each Part as a character
	temp_code=0;
	cnt=0;
	if(temph->depth>8)
	{
	cnt=temph->depth/8;
        if((temph->depth%8)>0)
	  cnt=cnt+1;	
   //Here cnt is Number of Bytes needed for Code
  //Writting For right side bytes First
	for(cnt=cnt-1;cnt>=0;cnt--)
	{
	 free(char_write);
	 char_write=(char *)malloc(1);
	 if(cnt>0)
	  temp_code=temph->code>>(8*cnt);
	 else
	  temp_code=temph->code;	 
	 temp_code=temp_code<<8;
	 temp_code=temp_code>>8;
	 *char_write=(char)temp_code;
	 if((write(fpW,char_write,1))!=1)
	 {
	  printf("\nFile writing error");
	  fcloseall();
	  exit(0);
	 }
	}
	//end of For Loop
      }
      //End of if depth>8 
      else
      {
	temp_code=temph->code;
	temp_code=temp_code<<8;
	temp_code=temp_code>>8;
	*char_write=(char)temp_code;
	if((write(fpW,char_write,1))!=1)
	{
	  printf("\nFile writing error");
	  fcloseall();
	  exit(0);
	}
      }
      //end of else of if depth > 8
      temph=temph->next;
     }
  //End of Write Header to New File
//============================================================================
 //Here We Read Each Character From Input File and Writes it's code to new File 
     /* replace andmask by var which will be written to file as char replace
     andmask=7<<3;replace 7 by andmask & 3 by current char depth
     andmask=andmask|3;replace 3 by current char code
     if andmask exited 256 then take rem=andmask-256
     write 256 as file char and assign andmask to rem and continue loop
    if andmask is 8 bits write to file
    */
    
   bit=0;
   mask=0;
   free(char_write);
   char_write=(char *)malloc(1);
   file_size=0;
   while((read(fpR,ch,1))!=0)
   {
     file_size=file_size+1;
     temph=head_header;
     //Code to search for Input file character in header
     while(temph!=NULL)
     {
       if(temph->ch==(*ch))
       {
	 //Here If Character from input file matches with header 
	 //Then fetch it's code and depth and corresponding code to New File
	 code=temph->code;
	 len=temph->depth;
	 break;
       }
       temph=temph->next;
      } 
     //end of search for Input file character in header
   mask=mask<<len;
   mask=excedify(mask);
   mask=mask|code;
   mask=excedify(mask);
  bit=bit+len;
  //If Constructed code is of 8 bit long then write it to New File 
  if(bit==8)
  {
    *char_write=(char)mask;
    if((write(fpW,char_write,1))!=1)
    {
      printf("\nFile writing error");
      fcloseall();
      exit(0);
    }
    mask=0;
    bit=0;
   }
  //End of bit==8
  //If Constructed code is > 8 bit long then write first 8 bits form left           as chacter to it to New File until less than 8 bits
   if(bit>8)
   {
     while(bit>8)
     {		
       rembit=32-bit;
       mask=mask<<rembit;
       mask=excedify(mask);
      tempmask=mask;
      tempmask=excedify(tempmask);
//Take Left most 8 bits and write to New File First
      tempmask=tempmask>>24;
      tempmask=excedify(tempmask);
      *char_write=(char)tempmask;
      if((write(fpW,char_write,1))!=1)
      {
        printf("\nFile writing error");
	fcloseall();
	exit(0);
      }
      mask=mask<<8;
      mask=excedify(mask);
      mask=mask>>8;
      mask=mask>>rembit;
      mask=excedify(mask);
     bit=bit-8;	
    }
    //end of while code length > 8 bits
   }
   //end of if code length > 8 bits
  } 
  //End of Read Input File 
 //==========================================================================
  //If some bits are remaining in code then write those to New File
   bit=8-bit;
   mask=mask<<bit;
   mask=excedify(mask);
   *char_write=(char)mask;
    if((write(fpW,char_write,1))!=1)
    {
      printf("\nFile writing error");
      fcloseall();
      exit(0);
     }
   }
   //End of Writing New File 
//============================================================================
 }
 //End of Reading Input file 
//============================================================================
fcloseall();
system("clear");
printf("\nGiven File is successfully Compressed with ''%s'' name \n",fnmW);
//make compressed file read only by system call chmod
/*if (chmod(fnmW, S_IREAD) != 0)
  {
    printf("\nFile Created But Unable to change file mode");
    getch();
    exit(0);
  } */
  //end of make compressed file read only by system call chmod
  return 0;
//End Of Compression Of Input File As New File
}
//End of Compress Function
//============================================================================
//Program Starts From Here : Entry Point
int main(int argc,char *argv[])
{
  char fnmW[15],*ch,*helpch;
  int fpR,infofd,helpfd,readcnt;
  struct list *head_list=NULL,*min1,*min2,*temp;
  struct header *temph;
  unsigned int newfilesize,headersize,tempheadersize,databytesize,tempdatabitsize;
  switch(argc)
  {  
   case 1 :
	  printf("\nInsufficient Arguments ");		
	  break;
   case 2 :
	  if(strcmp(argv[1],"-help")==0)
	  {
		system("clear");
		system("cat Compress.man");  
		break;  
	  }
	  if(strcmp(argv[1],"-info")==0)
	  {
		  system("clear");
		  system("cat info.info"); 
		  break;
	  }
	  //Create New File Name , if not specified    
  	  DirectoryOrFile(argv[1],1);
	  sscanf(argv[1],"%[^.]s",fnmW);
          strcat(fnmW,".cmp");
	  compress(argv[1],fnmW);
	  
	  break;
   case 3 :
          if(strcmp(argv[2],"-i")==0)
	  {
	  //New file size is combination of byte for 
	  //Total node(2)+exention(3)+original file size(4)+headersize(4)  
	   newfilesize=13;
	  //Now add bytes required to write header 
           if((fpR=open(argv[1],O_RDONLY))==-1)
           {
		printf("Enable To Open File %s \n",argv[1]);
		exit(0);
	   }
	   else
	   {
	   ch=(char *)malloc(1); 
           while((read(fpR,ch,1))!=0)
             make_list(&head_list,ch);
       //Find Min Two Node from list and Create Tree For Huffman & Create Codes
           temp=head_list;
           while(temp!=NULL)
           {
            min1=head_list;
            min2=head_list->next;
            if(find_min(&head_list,&min1,&min2)==1)
            {
              //Create Codes Here
             code_tree(min1,0,0);
             break;
            }
            //Creat Tree For Huffman Here
            create_tree(&head_list,&min1,&min2);
            temp=temp->next;
            }
        //End of Find Min Two Node from list and Create & Code Huffman Tree
	   
        //Code To Calculate Header Size & File Data size
            temph=head_header;
            headersize=0;
	    databytesize=0;
	    tempdatabitsize=0;
            tempheadersize=0;
            while (temph!=NULL)
            {
              if((temph->depth%8)>0)
                tempheadersize=(temph->depth/8)+2+1;
              else
                tempheadersize=(temph->depth/8)+2;
	      
	  //Here we calculate size for header data 
	      headersize=headersize+tempheadersize;
	      
	  //Here we calculate size for input file data after compress in bits
	      tempdatabitsize=tempdatabitsize+(temph->cnt*temph->depth);
	      
              temph=temph->next;
             }
	    //End of Reading Header & calculate Header size
	  //Here we calculate size for input file data after compress in bytes
	    if((tempdatabitsize%8)>0)
		 databytesize=(tempdatabitsize/8)+1;
	    else
		 databytesize=tempdatabitsize/8;
	   //Add  Header size and databytesize to newfilesize
	    //So final New File Size is
	   newfilesize=newfilesize+headersize;
	   newfilesize=newfilesize+databytesize;
	   system("clear");
	   printf("\nAfter Compressing File %s ",argv[1]);
	   printf("Compressed File size will be appx. %u bytes\n",newfilesize);
	  }
	  //End of file read else
	   break;	 
	  }
          //End of if argv[2] is -i	  
 //===========================================================================
	  else if(strcmp(argv[2],"-r")==0)
	  {
             sscanf(argv[1],"%[^.]s",fnmW);
			 strcat(fnmW,".neo");
		 compress(argv[1],fnmW);
		 ratio(argv[1],fnmW);
		 break;
	  }
	  else
	  {
		  printf("\nInvalid Command\n");
		  exit(0);
	  }

	  break;
   case 4:
	  DirectoryOrFile(argv[3],4);
	  if(strcmp(argv[2],"-n")==0)
	  {
			 sscanf(argv[3],"%[^.]s",fnmW);
			 strcat(fnmW,".neo");
		 compress(argv[1],fnmW);
		 break;
	  }
	  else
	  {
		  printf("\nInvalid Command\n");
		  exit(0);
	  }
	  break;
   default :
	  printf("\nInvalid Command\n");
	  break;
  }
  return 0;
}

